package model.algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import model.datastructure.AbstractBlock;
import model.datastructure.Block2D;
import model.datastructure.Field2D;
import model.datastructure.FieldSurface2D;
import model.datastructure.Fit;
import model.datastructure.Position2D;
import util.Util;

public abstract class AbstractAlgorithm {

	protected AbstractSurfaceIterator mSurfaceIterator;
	protected String name;

	public static final int LOOKAHEAD_PLACEONE = 0;
	public static final int LOOKAHEAD_PLACEALL = 1;

	/**
	 * @param iterator
	 */
	public AbstractAlgorithm( AbstractSurfaceIterator iterator ) {
		mSurfaceIterator = iterator;
	}

	/**
	 * Loops through list with blocks.
	 * 
	 * @param blocks - List with blocks.
	 * @throws Exception
	 */
	public void placeBlocks( Field2D field, List<Block2D> blocks, 
			int lookAhead, double maxSeconds, int lookAheadType ) 
	throws Exception {
		
		long start = System.nanoTime();

		/* incrementer to determine size of blocklist to be passed on */
		int lookAheadIncrementer = 0;

		/*
		 * deteremine the size of blocklist to be passed based on the lookahead
		 * type
		 */
		switch( lookAheadType ) {
		case LOOKAHEAD_PLACEONE :
			lookAheadIncrementer = 1;
			break;
		case LOOKAHEAD_PLACEALL :
			lookAheadIncrementer = 1 + lookAhead;
			break;
		default :
			throw new Exception( "LookAheadType not implemented: " + lookAheadType );
		}

		/* place blocks per amount determined by lookAheadIncrementer */
		for( int iBlocks = 0; iBlocks < blocks.size(); iBlocks += lookAheadIncrementer ) {
			if( ( System.nanoTime() - start ) / 1000000000 > maxSeconds ) {
				throw new Exception( toString() + "field width: " + field.getDimension().getWidth() + "\tlook ahead: (T " + lookAheadType + ") " + lookAhead + ", took too long." + " Made it to block number " + iBlocks);
			}
			/*
			 * place the block in the field, combined with the list of blocks we
			 * are looking ahead with
			 */
			int end = iBlocks + lookAhead + 1;
			if( end > blocks.size() ) {
				end = blocks.size();
			}
			
			List<Block2D> blockList = new ArrayList<Block2D>();
			
			for(int i = iBlocks; i < blocks.size() && blockList.size() <= lookAhead; i+=mSurfaceIterator.getLookaheadBlockStepSize()){
				blockList.add(blocks.get(i));
			}
			mSurfaceIterator.reset( field.getSurface(), blockList.get(0).getBlockType().getSurface(0) , false);
			placeBlock( field, blockList, lookAheadType );
		}
	}

	/**
	 * Places a block or a list with blocks, based on the lookaheadtype
	 * 
	 * @param field - field the block(s) will be placed on
	 * @param blocks - list with block(s) to be placed an looked ahead with
	 * @param lookAheadType - way of looking ahead
	 * @throws Exception - if lookaheadtype is not defined
	 */
	public void placeBlock( Field2D field, List<Block2D> blocks, int lookAheadType ) throws Exception {

		/* retrieve the result for simulating placing of all blocks in the list */
		LookAheadResult result = getBestPosition( field.getSurface(), new int[ field.getDimension().getWidth() ], blocks );

		int blockListEnd = 0;

		/* determine on base of the lookaheadtype if only one or all blocks have to be placed */
		switch( lookAheadType ) {
		case LOOKAHEAD_PLACEONE :
			blockListEnd = 1;
			break;
		case LOOKAHEAD_PLACEALL :
			blockListEnd = blocks.size();
			break;
		default :
			throw new Exception( "LookAheadType not implemented: " + lookAheadType );
		}

		/* Walk through the list of results and blocks, and place the blocks based on their fits */
		for( int index = 0; index < blockListEnd; index ++ ) {
			Fit fit = result.getFitList().get( index );
			AbstractBlock block = fit.getBlock();
			block.setPosition( new Position2D( fit.getxPosition(), fit.getYPosition() ) );
			block.setRotation( fit.getRotation() );
			field.placeBlock( block );
		}
	}

	/**
	 * Evaluates how the blocks to be looked ahead with are placed and returnes
	 * the evaluation for the placing of these blocks
	 * 
	 * @param fieldSurface
	 * @param emptySpace
	 * @param blocks
	 * @return
	 */
	public LookAheadResult getBestPosition( FieldSurface2D fieldSurface, 
			int[] emptySpace, List<? extends AbstractBlock> blocks ) {
		
		LookAheadResult result = new LookAheadResult();
		result.setEvaluation( Double.MAX_VALUE );
		Fit bestFoundFit = null;

		/* block to be evaluated now is the first in the list */
		AbstractBlock block = blocks.get( 0 );
		/*
		 * the list to be passed on (lookahead blocks) is the list without the
		 * first block
		 */
		List<? extends AbstractBlock> testBlocks = blocks.subList( 1, blocks.size() );

		/* get the fit's for the current block and evaluate the lookahead blocks */
		for( Fit fit : getFits( fieldSurface, block ) ) {

			/* we have reached the last block, no need to go into recursion here */
			if( blocks.size() == 1 ) {

				/* store the emptyspace and combine it for evaluation */
				int[] totalEmptySpace = Util.combine( emptySpace, fit.getEmptySpace() );
				double value = evaluate( fit.getSurface(), totalEmptySpace );
				if( value < result.getEvaluation() ) {
					result.setEvaluation( value );
					bestFoundFit = fit;
				}

				/* if this is not the last block, get into the recursion */
			} else {

				LookAheadResult value = getBestPosition( fit.getSurface(), 
						Util.combine( fit.getEmptySpace(), emptySpace ), testBlocks );
				if( value.getEvaluation() < result.getEvaluation() ) {
					result = value;
					bestFoundFit = fit;
				}
			}
		}

		result.addFit( bestFoundFit );
		return result;
	}

	/**
	 * returns the list of fits for the given block on the given surface
	 * 
	 * @param fieldSurface
	 * @param block
	 * @return
	 */
	public List<Fit> getFits( FieldSurface2D fieldSurface, AbstractBlock block ) {
		List<Fit> result = new ArrayList<Fit>();

		/* get rotations of the block and walk through them */
		int rotations = block.getBlockType().getNumberOfRotations();

		for( int iRotation = 0; iRotation < rotations; iRotation ++ ) {

			/* reset the iterator and pass it the blocksurface */
			mSurfaceIterator.reset( fieldSurface, block.getBlockType().getSurface( iRotation ) , true);
			while( mSurfaceIterator.hasNext() ) {

				int x = mSurfaceIterator.next();
				/*
				 * Match surface of block with the fieldSurface and store the
				 * placement variables in fit
				 */
				Fit fit = fieldSurface.match( block.getBlockType().getSurface( iRotation ), x );
				fit.setxPosition( x );
				fit.setRotation( iRotation );
				fit.setBlock( block );
				result.add( fit );
			}
		}
		return result;
	}

	/**
	 * 
	 * @param surface
	 * @param emptySpace
	 * @return
	 */
	public abstract double evaluate( FieldSurface2D surface, int[] emptySpace );

	@Override
	public String toString() {
		return name + "\t" + mSurfaceIterator + "\t";
	}

	/**
	 * Innerclass to store the results of lookahead recursion
	 * 
	 * @author mark
	 */
	public class LookAheadResult {

		private LinkedList<Fit> fitList;
		private double evaluation;

		public LookAheadResult() {
			fitList = new LinkedList<Fit>();
		}

		/**
		 * @return the fitList
		 */
		public List<Fit> getFitList() {
			return fitList;
		}

		/**
		 * Adds fit to the front of the list
		 * 
		 * @param fit
		 */
		public void addFit( Fit fit ) {
			fitList.addFirst( fit );
		}

		/**
		 * @return the evaluation
		 */
		public double getEvaluation() {
			return evaluation;
		}

		/**
		 * @param evaluation
		 *            the evaluation to set
		 */
		public void setEvaluation( double evaluation ) {
			this.evaluation = evaluation;
		}
	}

}